# -*- coding: utf-8 -*-
import ast
import time
import math
import random
import logging
import pandas as pd
from deap import algorithms, base, creator, tools
import multiprocessing
from lbs_service import get_travel_time
"""
将订单编号作为基因，手艺人作为种群
通过交换固定位置的订单编号，搜索更优解
种群基因形式(首位为手艺人编号，-1代表不可用时间)：
[1, -1, 0, 157, 157, 157, 157, 157, 0, 412, 412, 412, 412, 412, 0, 640, 640, 640, 640, 640, 0, 908, 908, 908, 908, 0]
[53, 0, 0, 164, 164, 164, 164, 0, 0, 418, 418, 418, 418, 0, 0, 646, 646, 646, 646, 0, 0, 0, 0, 0, 0, -1]
抽取手艺人的开放时间，需要对关闭时间做检查和限制
（去掉关闭和不可用时间）
"""
logging.basicConfig(level=logging.DEBUG, format='%(asctime)s - %(name)s - %(levelname)s - %(lineno)d: %(message)s')
logger = logging.getLogger(__name__)

df_artisans = pd.read_csv('data/sample/artisans.csv')
df_orders = pd.read_csv('data/sample/orders.csv')
city_id = '2'
# df_orders = pd.read_csv('data/sample/orders.csv', nrows=100)
# df_times = pd.read_csv('data/sample/travel_times.csv')
df_times = None
# Create Fitness and Individual Classes
# creator.create('FitnessMax', base.Fitness, weights=(1.0,))
# creator.create('Individual', list, fitness=creator.FitnessMax)


def create_artisan(k):
    gene = df_artisans['genes'].values[k]
    return gene


class IndividualList(list):
    """
    A subclass of list that can accept additional attributes.
    Should be able to be used just like a regular list.

    The problem:
    a = [1, 2, 4, 8]
    a.x = "Hey!" # AttributeError: 'list' object has no attribute 'x'

    The solution:
    a = L(1, 2, 4, 8)
    a.x = "Hey!"
    print a       # [1, 2, 4, 8]
    print a.x     # "Hey!"
    print len(a)  # 4

    You can also do these:
    a = L( 1, 2, 4, 8 , x="Hey!" )                 # [1, 2, 4, 8]
    a = L( 1, 2, 4, 8 )( x="Hey!" )                # [1, 2, 4, 8]
    a = L( [1, 2, 4, 8] , x="Hey!" )               # [1, 2, 4, 8]
    a = L( {1, 2, 4, 8} , x="Hey!" )               # [1, 2, 4, 8]
    a = L( [2 ** b for b in range(4)] , x="Hey!" ) # [1, 2, 4, 8]
    a = L( (2 ** b for b in range(4)) , x="Hey!" ) # [1, 2, 4, 8]
    a = L( 2 ** b for b in range(4) )( x="Hey!" )  # [1, 2, 4, 8]
    a = L( 2 )                                     # [2]
    """
    def __new__(self, *args, **kwargs):
        return super(IndividualList, self).__new__(self, args, kwargs)

    def __init__(self, *args, **kwargs):
        if len(args) == 1 and hasattr(args[0], '__iter__'):
            list.__init__(self, args[0])
        else:
            list.__init__(self, args)
        self.__dict__.update(kwargs)

    def __call__(self, **kwargs):
        self.__dict__.update(kwargs)
        return self


def get_travel_time_df(p1, p2, start):
    global df_times
    try:
        travel_times = df_times[(df_times['p1'] == p1) & (df_times['p2'] == p2)]
        travel_times['start_time'] = travel_times['start_time'].apply(lambda x: int(x) - int(start))
        best_time = travel_times['start_time'].abs().sort_values()[0]
    except:
        best_time = 0
    return best_time


def time_utilization(individual):
    """
    评价个体的好坏，可观察该个体的时间利用率
    路程时间利用率 = 订单数量/路程时间
    交叉和突变时也要检查
    :param individual:
    :return:
    """
    global df_artisans, df_orders, city_id
    error_routes = False
    total_time = 0
    # 检查时间窗口是否满足
    print('check gene: ' + str(individual))
    artisan_orders = []
    artisan_id = individual[0]
    order_nums = len(set([x for x in individual[1:] if int(x) > 0]))
    for order_id in individual[1:]:
        if order_id > 0:
            if len(artisan_orders) > 0:
                pre_order_id = artisan_orders[-1]
                pre_order = df_orders.iloc[pre_order_id]
            else:
                # 如果是该手艺人第一单
                pre_order = df_artisans.iloc[artisan_id]
            now_order = df_orders.iloc[order_id]
            travel_time = 0
            if pre_order is not None:
                # 排除预约时间有冲突的情况
                try:
                    now_start = int(now_order['start'])
                except Exception as e:
                    logger.exception(e)
                    now_start = 0
                pre_time = pre_order['stop']
                if now_start < pre_time:
                    print('order[' + str(order_id) + '] service time ' + str(now_start) + ' < artisan[' + str(
                        artisan_id) + '] pre time ' + str(pre_time))
                    error_routes = True
                    break
                # 排除路程时间不够的情况
                try:
                    p1 = str(pre_order['lon']) + ',' + str(pre_order['lat'])
                    p2 = str(now_order['lon']) + ',' + str(now_order['lat'])
                    start = str(math.floor((now_order['start']/(60 * 60) - 1) + 9)) + ":00"
                    interval_time = int(now_order['start']) - int(pre_order['stop'])
                    travel_time = get_travel_time(city_id, p1, p2, start)
                    print('get travel_time: ' + str(travel_time))
                except Exception as e:
                    logger.exception(e)
                    travel_time = 0
                if travel_time > interval_time:
                    print('order[' + str(order_id) + '] interval time ' + str(interval_time) + ' < artisan[' + str(
                        artisan_id) + '] travel time ' + str(travel_time))
                    error_routes = True
                    break
            total_time += travel_time
    if error_routes:
        # print('error routes')
        return None
    if total_time > 0:
        utilization = order_nums/total_time
        print('find one feasible solution, fitness: ' + str(utilization))
    else:
        utilization = None
    return utilization


def eval_vrptw(individual):
    """
    进化过程评价
    :param individual: 个体对象
    :param instance: 个体相关数据
    :return:
    """
    usage = time_utilization(individual)
    if usage is None:
        usage = 0
    return usage,


class IndividualFitness(base.Fitness):
    weights = (1,)

    def __init__(self, *args, **kwargs):
        base.Fitness.__init__(self, *args, **kwargs)


def create_individual(x):
    x = ast.literal_eval(x)
    fitness = eval_vrptw(x)
    genes = IndividualList(x, fitness=IndividualFitness(values=fitness))
    # genes.fitness.weights = (1.0,)
    return genes


df_artisans['genes'] = df_artisans['genes'].apply(create_individual)


def create_artisans(n=100):
    genes = df_artisans['genes'].values
    return genes


def drop_duplicate(ind_list):
    distinct_list = []
    for i in ind_list:
        if i not in distinct_list:
            distinct_list.append(i)
    return distinct_list


def genes_to_align(ind1, ind2):
    """
    基因二次编码
    步骤：
     1.去掉同为0部分
     2.左遍历，尾对齐
     3.右遍历，首对齐
     4.找出可合并的订单
     5.替换合并订单编号
     6.去除重复项
    :param ind1:
    :param ind2:
    :return:
    """
    # 1.去掉同为0部分
    # [1, 1, 2, 0, 0, 3, 3, 7, 9, 0, 10, 10]
    # [4, 0, 5, 5, 6, 6, 0, 0, 8, 8, 8, 0]
    try:
        i1_align, i2_align = zip(*[(i1, i2) for i1, i2 in zip(ind1, ind2) if (i1 + i2) > 0])
        i1_align = list(i1_align)
        i2_align = list(i2_align)
    except Exception as e:
        i1_align = [0]
        i2_align = [0]
        # logger.debug(ind1)
        # logger.debug(ind2)
        logger.exception(e)

    # 2.左遍历，尾对齐
    # [1,1,2,2,0,3,3,7,9,9,10,10]
    # [4,4,5,5,6,6,6,0,8,8,8,8]
    i1_pre_dna = 0
    i2_pre_dna = 0
    for i in range(len(i1_align)):
        if i1_align[i] == i1_pre_dna or i2_align[i] == i2_pre_dna:
            if i1_align[i] == 0:
                i1_align[i] = i1_pre_dna
            if i2_align[i] == 0:
                i2_align[i] = i2_pre_dna
        # print("i1_align[" + str(i) + "]=" + str(i1_align[i]) + " i1_pre_dna=" + str(i1_pre_dna))
        # print("i2_align[" + str(i) + "]=" + str(i2_align[i]) + " i2_pre_dna=" + str(i2_pre_dna))
        i1_pre_dna = i1_align[i]
        i2_pre_dna = i2_align[i]

    # 3.右遍历，首对齐
    # [1, 1, 2, 2, 3, 3, 3, 7, 9, 9, 10, 10]
    # [4, 4, 5, 5, 6, 6, 6, 0, 8, 8, 8, 8]
    i1_pre_dna = 0
    i2_pre_dna = 0
    for i in range(len(i1_align)-1, -1, -1):
        if i1_align[i] == i1_pre_dna or i2_align[i] == i2_pre_dna:
            if i1_align[i] == 0:
                i1_align[i] = i1_pre_dna
            if i2_align[i] == 0:
                i2_align[i] = i2_pre_dna
        i1_pre_dna = i1_align[i]
        i2_pre_dna = i2_align[i]

    # 4.找出可合并的订单
    # [9,10]
    i1_combine_dna = []
    i1_combine_name = []
    i2_combine_dna = []
    i2_combine_name = []
    i1_set = set(i1_align)
    i2_set = set(i2_align)
    for s in i2_set:
        s_len = i2_align.count(s)
        s_start = i2_align.index(s)
        s_end = s_start + s_len
        if s_len >= 2:
            i1_combines = [i for i in i1_set if i1_align.index(i) >= s_start and i1_align.index(i) + i1_align.count(i) <= s_end]
            if len(i1_combines) > 1:
                i1_combine_dna.append(i1_combines)
                i1_combine_name.append(int('000'.join(str(i) for i in i1_combines)))
    for s in i1_set:
        s_len = i1_align.count(s)
        s_start = i1_align.index(s)
        s_end = s_start + s_len
        if s_len >= 2:
            i2_combines = [i for i in i2_set if i2_align.index(i) >= s_start and i2_align.index(i) + i2_align.count(i) <= s_end]
            if len(i2_combines) > 1:
                i2_combine_dna.append(i2_combines)
                i2_combine_name.append(int('000'.join(str(i) for i in i2_combines)))

    # 5.合并DNA
    # [1, 1, 2, 2, 3, 3, 3, 7, 900010, 900010, 900010, 900010]
    # [4, 4, 5, 5, 6, 6, 6, 0, 8, 8, 8, 8]
    for i in range(len(i1_align)):
        for j in range(len(i1_combine_dna)):
            if i1_align[i] in i1_combine_dna[j]:
                i1_align[i] = i1_combine_name[j]
    for i in range(len(i2_align)):
        for j in range(len(i2_combine_dna)):
            if i2_align[i] in i2_combine_dna[j]:
                i2_align[i] = i2_combine_name[j]

    # 6.去除重复项
    # [1, 2, 3, 7, 90010]
    # [4, 5, 6, 0, 8]
    i1_aligned = drop_duplicate(i1_align)
    i2_aligned = drop_duplicate(i2_align)

    return i1_aligned, i2_aligned


def align_to_genes(aligned, no_work_index, order_index, order_hour):
    """
    二次编码解码
    :param aligned:
    :param no_work_index: 非工作时间
    :param order_index:
    :param order_hour:
    :return:
    """
    aligns = []
    # 解开组合编码
    for a in aligned:
        if a > 10000:
            aligns.extend(str(a).split('000'))
        else:
            aligns.append(str(a))
    gens = []
    order_id = 0
    repeat = 0
    # 开始组装
    for half_hour in range(12 * 2):
        if half_hour in no_work_index:
            code = -1
        else:
            code = 0
        if repeat > 0:
            code = order_id
            repeat -= 1
        else:
            orders = [k for k, v in order_index.items() if v == half_hour]
            if orders is not None and len(orders) > 0:
                for a in aligns:
                    if a in orders:
                        repeat = order_hour[a] - 1
                        order_id = int(a)
                        code = order_id
        gens.append(code)
    return gens


def order_time_matched(ind1, ind2):
    """
    交叉方法
    手艺人订单基因中的订单时间必须匹配，才能交换变异
    0.首先排除两个个体不可用时间
    目前只考虑三种可交换的情况：
    1.个体时间互补：个体有对应的空闲时间容纳另一个体的订单；
    2.个体时间对应：个体1与个体2中的订单占用时间可包含；
    3.一对多订单变异（可选）；
    原始基因：
    [-1,1,1,0,2,0,0,0,3,3,0,7,0,9,0,10,10]
    [-1,4,0,0,5,5,0,6,6,0,0,0,0,8,8,8,0]
    二次编码
    可用于交换变异的基因别名：
    [1,2,3,7,90010]
    [4,5,6,0,8]
    :param ind1:
    :param ind2:
    :return:
    """
    # logger.debug('old gens:')
    # logger.debug(ind1)
    # logger.debug(ind2)
    no_work_index1 = [i for i in range(len(ind1) - 1) if ind1[i+1] == -1]
    no_work_index2 = [i for i in range(len(ind2) - 1) if ind2[i+1] == -1]
    # 去除不可用时间
    no_work_index = [i for i in range(len(ind1) - 1) if ind1[i+1] == -1 or ind2[i+1] == -1]
    work_ind1 = [ind for i, ind in enumerate(ind1[1:]) if i not in no_work_index]
    work_ind2 = [ind for i, ind in enumerate(ind2[1:]) if i not in no_work_index]
    # 用字典记住订单的位置和长度，方便解码
    # order_index: {'1': 1, '2': 4, '3': 8}
    # order_hour: {'1': 2, '2': 1, '3': 2}
    order_index = {str(ind): i for i, ind in enumerate(work_ind1) if ind > 0}
    order_index2 = {str(ind): i for i, ind in enumerate(work_ind2) if ind > 0}
    order_index.update(order_index2)

    order_hour = {str(ind): ind1[1:].count(ind) for i, ind in enumerate(work_ind1) if ind > 0}
    order_hour2 = {str(ind): ind2[1:].count(ind) for i, ind in enumerate(work_ind2) if ind > 0}
    order_hour.update(order_hour2)

    i1_aligned, i2_aligned = genes_to_align(work_ind1, work_ind2)
    if len(i1_aligned) >= 1 and len(i1_aligned) == len(i2_aligned):
        # logger.debug(i1_aligned)
        # logger.debug(i2_aligned)
        # 使用基因别名实现 均匀交叉
        ind_prob = 1 / len(i1_aligned)
        i1, i2 = tools.cxUniform(i1_aligned, i2_aligned, ind_prob)
        # logger.debug('genes mated:')
        # logger.debug(i1)
        # logger.debug(i2)
        ind1[1:] = align_to_genes(i1, no_work_index1, order_index, order_hour)
        ind2[1:] = align_to_genes(i2, no_work_index2, order_index, order_hour)
    # logger.debug('new gens:')
    # logger.debug(ind1)
    # logger.debug(ind2)
    return ind1, ind2


def no_mutate(individual):
    # new_individual = tools.mutShuffleIndexes(individual, indpb = mut_pb)
    return individual


def ga_vrptw(pool_size, pop_size, cx_pb, mut_pb, gen_size):
    """
    遗传算法主程序
    :param pool_size: 线程池数量
    :param pop_size: 种群数量
    :param cx_pb: 交叉概率
    :param mut_pb: 突变概率
    :param gen_size: 进化次数
    :return:
    """
    toolbox = base.Toolbox()
    if pool_size <= 0:
        pool = multiprocessing.Pool()
    else:
        pool = multiprocessing.Pool(pool_size)
    toolbox.register("map", pool.map)
    # 从手艺人编号中随机选取
    # toolbox.register('indexes', random.choices, range(ind_size), k=ind_size)
    # 生成独立个体
    # toolbox.register('individual', tools.initIterate, create_artisan, toolbox.indexes)
    # toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.partition)
    # 定义种群生成器
    # 二次派单问题中，我们不需要随机生成N个种群，只需要在现有固定接单手艺人的基础上交叉变异即可
    # toolbox.register('population', tools.initRepeat, list, toolbox.individual)
    toolbox.register('population', create_artisans)
    # 生成种群
    pop = toolbox.population(n=pop_size)
    # pop = create_artisans()
    # print(pop)
    # 定义评价方法
    toolbox.register('evaluate', eval_vrptw)
    # 定义选择方法
    # toolbox.register('select', tools.selRoulette)
    # 每次选择最差配种
    toolbox.register('select', tools.selWorst)
    # 定义交叉方法
    toolbox.register('mate', order_time_matched)
    # 定义突变方法
    # 订单时间位置特殊，突变会导致时间窗口被破坏，不进行突变
    toolbox.register('mutate', no_mutate)
    # Begin the evolution
    # hof = tools.HallOfFame(1)
    # stats = tools.Statistics(lambda ind: ind.fitness.values)
    # stats.register("avg", np.mean)
    # stats.register("std", np.std)
    # stats.register("min", np.min)
    # stats.register("max", np.max)
    # pop, log = algorithms.eaSimple(pop, toolbox, cxpb=cx_pb, mutpb=mut_pb, ngen=gen_size, stats=stats, halloffame=hof, verbose=True)
    # return pop, log
    g = 0
    fitnesses = list(toolbox.map(toolbox.evaluate, pop))
    for ind, fit in zip(pop, fitnesses):
        ind.fitness.values = fit
    fits = [ind.fitness.values[0] for ind in pop]
    best_fit = sum(fits)
    best_fits = [best_fit]
    best_solution = []
    # 第一代种群中 未找到有效派单方案
    if len(fits) == 0:
        return "no feasible solution found, please increase population size."
    while len(fits) > 0 and g < gen_size:
        # A new generation
        g = g + 1
        print("-- Generation %i --" % g)
        # Select the next generation individuals
        offspring = toolbox.select(pop, len(pop))
        # 保留未选择的父代个体
        pre_pop = [x for x in pop if x not in offspring]
        # Clone the selected individuals
        offspring = list(map(toolbox.clone, offspring))
        print("select " + str(len(offspring)) + " individuals")
        print("remain " + str(len(pre_pop)) + " individuals")
        # Apply crossover and mutation on the offspring
        for child1, child2 in zip(offspring[::2], offspring[1::2]):
            # cross two individuals with probability CXPB
            if random.random() < cx_pb:
                toolbox.mate(child1, child2)
                # fitness values of the children
                # must be recalculated later
                del child1.fitness.values
                del child2.fitness.values
        # Evaluate the individuals with an invalid fitness
        invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
        fitnesses = map(toolbox.evaluate, invalid_ind)
        for ind, fit in zip(invalid_ind, fitnesses):
            ind.fitness.values = fit
        print("  Evaluated %i individuals" % len(invalid_ind))
        # The population is entirely replaced by the offspring
        pop = list(offspring)
        pop.extend(pre_pop)
        # Gather all the fitnesses in one list and print the stats
        fits = [ind.fitness.values[0] for ind in pop]
        if best_fit < sum(fits):
            best_fit = sum(fits)
            best_fits.append(best_fit)
            best_solution = pop
    pool.close()
    print("-- End of (successful) evolution --")
    # 此处不同于传统的进化算法挑选个体
    # 而是挑选进化过程中得分最高的某一代
    if best_fit > 0:
        print("Best population is %s, %s" % (best_solution, best_fit))
        best_df = pd.DataFrame(data=best_solution)
        best_df.to_csv('data/best_result.csv')
        eval_df = pd.DataFrame({'fits': best_fits})
        eval_df.to_csv('data/eval_fits.csv')


def train(pool_size, gen_size=5):
    random.seed(3)
    pop_size = len(df_artisans)
    # 交叉概率(意味着50%手艺人的订单会发生交叉)
    cx_pb = 0.5
    # 突变概率
    mut_pb = 0.2
    # Global creation of the individuals for GA
    ga_vrptw(
        pool_size=pool_size,
        pop_size=pop_size,
        cx_pb=cx_pb,
        mut_pb=mut_pb,
        gen_size=gen_size
    )


if __name__ == '__main__':
    # 正式运行
    tic = time.clock()
    train(30, 2000)
    # train(0, 10)
    print('Computing Time: %s' % (time.clock() - tic))

    # 测试评价函数
    # gene = [5, 4, 4, 20, 16, 12, 14, 9, 17, 10, 17, 10, 9, 10, 19, 17, 2, 10, 3, 7]
    # gene = [3, 6, 6, 10, 2, 4, 4, 5, 7, 10]
    # total_time = genes_to_time(gene)
    # print(total_time)

    # 测试基因二次编码
    # ind1 = [1, 1, 2, 0, 0, 3, 3, 7, 9, 0, 10, 10]
    # ind2 = [4, 0, 5, 5, 6, 6, 0, 0, 8, 8, 8, 0]
    # i1_align, i2_align = genes_to_align(ind1, ind2)
    # print(i1_align)
    # print(i2_align)
